#!/usr/bin/env python3.3

#
#  Filename: e61.py
#  Author  : lukas singer
#
#  Comment : Created by createSolution.sh
#

#import euler
from euler import *

def fn(n):
  return (3,triangular(n)), (4,square(n)), (5,pentagonal(n)), (6,hexagonal(n)), (7,heptagonal(n)), (8,octagonal(n))
   
def next(types, data):
  if len(types)==6 and data[0]//100 == data[-1]%100:
    print(data, sum(data))
    exit()
  else:
    for t, n in ds.get((types[-1], data[-1]), []):
      if t not in types:
        next(types+[t], data+[n])
 
ds={}
def pe61():
  p = []          #build a list of polygonal numbers with their type (type, pnum)
  n = 19          #first n for octogonal number > 999
                                        
  while n<141:    #last n for triangle numbers < 10000
    for type, data in fn(n):
      if 1000 <= data <= 9999 and data%100 > 9:
        p.append( (type, data) ) 
    n+=1
                                                             
  for t1, d1 in p:
    for t2, d2 in p:
      if t1 != t2 and d1%100 == d2//100:
        ds[t1, d1] = ds.get((t1, d1),[]) + [(t2, d2)] 
  for type, data in ds: next([type],[data])

if __name__=="__main__":
  pe61()

